package com.ntd.study.algorithm.sort.impl;

import cn.hutool.core.util.ArrayUtil;
import com.ntd.study.algorithm.sort.Sort;

import java.util.Arrays;
import java.util.function.BiFunction;

/**
 * 归并
 *
 * @author liuwenju
 * @date 2021/4/22
 */
public class SortMerge<T> implements Sort<T> {

    private BiFunction<T, T, Boolean> sort;

    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        this.sort = sort;
        return this.sort(arrays);
    }

    public T[] sort(T[] arrays) {
        if (arrays.length < 2) {
            return arrays;
        }
        int middle = (int) Math.floor(arrays.length / 2);

        T[] left = Arrays.copyOfRange(arrays, 0, middle);
        T[] right = Arrays.copyOfRange(arrays, middle, arrays.length);

        return merge(sort(left), sort(right));
    }

    private T[] merge(T[] left, T[] right) {
        T[] result = ArrayUtil.newArray(left[0].getClass(), left.length + right.length);
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (!sort.apply(left[0], right[0])) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }
}
